package leetcode_101_120;

import leetcode_81_100.*;
import org.junit.Test;
import utils.ListNode;
import utils.Node;
import utils.TreeNode;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;

public class Tset6 {
    @Test
    //对称二叉树
    public void test101(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(4);
        TreeNode treeNode3=new TreeNode(1);

        TreeNode treeNode4=new TreeNode(1);
        TreeNode treeNode5=new TreeNode(4);

        TreeNode treeNode6=new TreeNode(2);
        TreeNode treeNode7=new TreeNode(2);

//        TreeNode treeNode8=new TreeNode(4);
//        TreeNode treeNode9=new TreeNode(4);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.right=treeNode4;
        //treeNode2.right=treeNode5;

        treeNode3.right=treeNode5;
        //treeNode3.right=treeNode7;

        treeNode4.left=treeNode6;
        treeNode5.left=treeNode7;

        System.out.println(new isSymmetric_101().isSymmetric(treeNode1));
    }

    @Test
    //二叉树的层序遍历
    public void test102(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(2);

        TreeNode treeNode4=new TreeNode(3);
        TreeNode treeNode5=new TreeNode(3);

        TreeNode treeNode6=new TreeNode(4);
        TreeNode treeNode7=new TreeNode(4);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        System.out.println(new levelOrder_102().levelOrder(treeNode1));
    }

    @Test
    //二叉树的锯齿形层序遍历
    public void test103(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);

        TreeNode treeNode4=new TreeNode(3);
        TreeNode treeNode5=new TreeNode(3);

        TreeNode treeNode6=new TreeNode(4);
        TreeNode treeNode7=new TreeNode(4);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        System.out.println(new zigzagLevelOrder_103().zigzagLevelOrder(treeNode1));
    }

    @Test
    //二叉树的最大深度
    public void test104(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);

        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(4);

        TreeNode treeNode6=new TreeNode(5);
        TreeNode treeNode7=new TreeNode(5);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        System.out.println(new maxDepth_104().maxDepth(treeNode1));
    }

    @Test
    //从前序与中序遍历序列构造二叉树
    public void test105(){
        int[]a={1,2,4,3};
        int[]b={1,2,3,4};
        System.out.println(new buildTree_105().buildTree(a,b));
    }

    @Test
    //从前序与中序遍历序列构造二叉树
    public void test106(){
        int[]a={9,3,15,20,7};
        int[]b={9,15,7,20,3};
        System.out.println(new buildTree_106().buildTree(a,b));
    }

    @Test
    //二叉树的层序遍历 II
    public void test107(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);

        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(4);

        TreeNode treeNode6=new TreeNode(5);
        TreeNode treeNode7=new TreeNode(5);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        System.out.println(new levelOrderBottom_107().levelOrderBottom(treeNode1));
    }

    @Test
    //将有序数组转换为二叉搜索树
    public void test108(){
        int []nums = {-10,-3,0,5,9};
        System.out.println(new sortedArrayToBST_108().sortedArrayToBST(nums));
    }

    @Test
    //有序链表转换二叉搜索树
    public void test109(){
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(3);
        ListNode listNode4=new ListNode(4);
        ListNode listNode5=new ListNode(5);
        ListNode listNode6=new ListNode(6);
        ListNode listNode7=new ListNode(7);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;

        System.out.println(new sortedListToBST_109().sortedListToBST(listNode1));
    }

    @Test
    //判断是否是高度平衡的二叉树
    public void test110(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);

        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(4);

        TreeNode treeNode6=new TreeNode(5);
        TreeNode treeNode7=new TreeNode(5);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        System.out.println(new isBalanced_110().isBalanced(treeNode1));
    }

    @Test
    //找出二叉树最小深度
    public void test111(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);

        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(4);

        TreeNode treeNode6=new TreeNode(5);
        TreeNode treeNode7=new TreeNode(5);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        System.out.println(new minDepth_111().minDepth(treeNode1));
    }

    @Test
    //路径总和
    public void test112(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);

        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(4);

        TreeNode treeNode6=new TreeNode(5);
        TreeNode treeNode7=new TreeNode(5);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        System.out.println(new hasPathSum_112().hasPathSum(treeNode1,7));
    }

    @Test
    //路径总和2
    public void test113(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(3);
        TreeNode treeNode3=new TreeNode(2);

        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(4);

        TreeNode treeNode6=new TreeNode(5);
        TreeNode treeNode7=new TreeNode(5);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        System.out.println(new pathSum_113().pathSum(treeNode1,8));
    }

    @Test
    //二叉树展开为单链表
    public void test114(){
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);

        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(4);

        TreeNode treeNode6=new TreeNode(5);
        TreeNode treeNode7=new TreeNode(5);

        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;

        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;

        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;

        new flatten_114().flatten(treeNode1);
    }

    @Test
    //子序列中出现的个数
    public void test115(){
        String s = "rabbbit", t = "rabbit";
        System.out.println(new numDistinct_115().numDistinct2(s,t));
    }

    @Test
    //填充完美二叉树下一个右侧节点指针
    public void test116(){
        Node Node1= new Node(1);
        Node Node2= new Node(2);
        Node Node3=new Node(3);

        Node Node4=new Node(4);
        Node Node5=new Node(4);

        Node Node6=new Node(5);
        Node Node7=new Node(5);

        Node1.left=Node2;
        Node1.right=Node3;

        Node2.left=Node4;
        Node2.right=Node5;

        Node3.left=Node6;
        Node3.right=Node7;

        new connect_116().connect(Node1);
    }
    @Test
    //填充二叉树下一个右侧节点指针
    public void test117(){
        Node Node1= new Node(1);
        Node Node2= new Node(2);
        Node Node3=new Node(3);

        Node Node4=new Node(4);
        Node Node5=new Node(4);

        Node Node6=new Node(5);
        Node Node7=new Node(5);

        Node1.left=Node2;
        Node1.right=Node3;

        Node2.left=Node4;
        Node2.right=Node5;

        Node3.left=Node6;

        new connect2_117().connect(Node1);
    }

    @Test
    //杨辉三角
    public void test118(){
        System.out.println(new generate_118().generate(5));
    }
    @Test
    //杨辉三角2
    public void test119(){
        System.out.println(new generate_118().getRow(5));
    }

    @Test
    //杨辉三角2
    public void test120(){
        List<List<Integer>> triangle=new ArrayList<>();
        List<Integer>list1=new ArrayList<>();
        list1.add(2);
        List<Integer>list2=new ArrayList<>();
        list2.add(3);
        list2.add(4);
        List<Integer>list3=new ArrayList<>();
        list3.add(6);
        list3.add(5);
        list3.add(7);
        List<Integer>list4=new ArrayList<>();
        list4.add(4);
        list4.add(1);
        list4.add(8);
        list4.add(3);
        triangle.add(list1);
        triangle.add(list2);
        triangle.add(list3);
        triangle.add(list4);
        System.out.println(new minimumTotal_120().minimumTotal3(triangle));
    }
}
